Subject: Loop prevention ideas

From: [email-masked]
Date: Tue, 17 May 94 17:53:35 EDT

At the Anaheim AIW, I said IBM would possibly take another look at some
sort of "heartbeat" solution to the looping problem.  I have spent some
time on it and, with feedback from others on the team, have a general
approach to suggest.  This isn't really a "proposal" yet because it
needs more refinement, but I thought I would put it out so people can
evaluate whether this is the direction they would like to go.

If these ideas hold together and seem worth pursuing, my opinion is
that interested persons should work together to produce a complete
proposal for "release 2" of the standardization effort.  It would take
more effort than I think it's worth right now trying to complete this
for the June AIW, and would divert energy from the critical RIGlets
(connect, capabilities, flow control).  I look forward to seeing what
everyone else thinks, but I will not be able to respond to questions
until next week.

Peter Gayek
IBM Corp.
----------------------- rough proposal -----------------------------

Objective
=========
Devise an algorithm which a DLSw node runs at the end of capability
exchange with a new potential partner.  The algorithm determines
whether the new transport connection establishes a loop in the
previously loop-free DLSw topology.  If a loop is established, the
transport connection is disabled for DLSw circuit establishment.

Acheiving load balancing across simultaneously active parallel paths
is NOT an objective of this solution.  The intent is not to allow
parallel paths.

Handling changes to the LAN topology (bridges added or removed) is an
eventual objective of this solution.

Basic Concepts
==============
- A "LAN region" is a set of LANs bridged together, and is known by
  a "LAN region id", which could be a number or a short name.  All
  DLSw nodes attached to the same LAN region must know it by the same
  id.  In the worst case this would be by coordinated configuration,
  but we think there should be a broadcast distribution mechanism.
- A single group address is required for DLSw.  All DLSw nodes open
  this group address on at least all TB ports, both for loop detection
  purposes and to set/learn the LAN region id.
- "Disabling" a transport connection, as mentioned above, means not
  using it for SSP circuit establishment flows.  One could take it
  down or just leave it up and not use it - we prefer the latter.  In
  either case one would retry the loop checking periodically.

Reference Configuration
=======================
The following picture shows a bunch of loops which would be avoided
by application of different pieces of the algorithm.  DLSw routers are
labelled with letters, LAN regions with numbers.  Two LAN regions
attached to the same router are not bridged by that router (if they
were, they would be one LAN region).  Dotted lines between routers
are partner relations, not physical connections.

   1  |----- A ......... C
             A ......    C -----|
      |----- A ..   :    C      |  4
   2  |         :   :           |
      |----- B ..   :... D -----|
             B ......... D
   3  |----- B ......    D -----|  5
                    :
                    :... E -----|  6

The General Scheme
==================

TRANSPORT CONNECTION ESTABLISHMENT:

1) All DLSw nodes learn the LAN regions to which each of their LAN
   ports is attached, before starting up any DLSw transport connections.

2) As part of capability exchange, each DLSw node reports to its
   potential partner a list of all the LAN regions to which it is
   attached.  This should not be a very long list, since it is limited
   by the number of bridge-grouped physical LAN ports on the box.
   Each node keeps track of:
     LAN regions it is attached to
     LAN regions each of its partners is attached to

3) At the end of capability exchange but before using the transport
   connection to carry any CURs, each of the two potential partners
   independently applies the following rules in order:

     a) "If the potential partner is attached to a LAN region that
        I am attached to, disable the transport connection".

        The node compares the partner's list of LAN regions with its
        own and sees if there are any matches.

        In the example diagram, this test would disallow the A-B
        transport, since routers A and B are both on LAN region 2.

     b) "If the potential partner is attached to a LAN region to which
        I have an active (enabled) partner already attached, disable
        the transport connection".

        The node compares the pot. partner's LAN region list with the
        lists it saved from capex with its other partners and sees if
        there are any matches.

        In the example diagram, if A-C were already active this test
        would disallow A-D, and vice versa.  If B-D were already active
        this test would disallow A-D, and vice versa.

     c) "If the potential partner is attached to a LAN region on which
        another DLSw node on one of my LAN regions has a partner,
        disable the transport connection".

        The node broadcasts a loop detection UI frame on all its LAN
        regions, addressed to the DLSw group address.  The frame
        essentially asks: "Do you have a partner attached to any of
        the following LAN regions", and includes the list of LAN regions
        just received from capex and a transport connection id.  The
        sending node retries this frame several times and waits for
        a reply.  No reply implies no loop formed.  A late reply
        causes a transport connection just deemed "ok" to be disabled.

        Receiving nodes on the LAN each check the their list of partner
        LAN regions against the list in the loop detection frame and
        reply only if there is some intersection.

        If two nodes each send a loop detection frame at about the
        same time, they each compare the two transport connection id's
        to resolve the race.  The endpoints of the transport connection
        that wins (will come up) are the ones that send a reply to the
        loop detection frame.

        In the example diagram, if A-C or A-D were already active this
        procedure would disallow B-D, and vice versa.

   If these three rules are found not to disable the transport connect-
   tion, then it is made fully operational for exchange of DLSw circuit
   establishment frames.

LAN REGION ID COORDINATION:

To be truly useful, this scheme cannot depend on coordinated, static,
configuration of LAN regions.  A simple Hello message scheme like the
one used in the 802.1 spanning tree algorithm would work here.  All
DLSw nodes on a LAN would listen while the one with the highest/lowest
MAC address broadcasts the LAN region id to the DLSw group address.
If the hello messages stop, the DLSw nodes would compete briefly until
a new broadcaster was elected.  If two LAN regions were joined, one
of the broadcasters would drop out and the listeners would note the
new LAN region id.

RUN-TIME CAPABILITIES EXCHANGE:

In order to support changes to LAN topology such as the merging or
separation of LAN regions when bridges go up or down (or previously
unbridged ports on a DLSw brouter being bridged), it is essential
that loop-preventing DLSw nodes also support the run-time exchange
of the capex CVs containing the LAN region id lists.  They need
not support run-time changes of other optional capex CVs.

Receipt of run-time LAN region lists would require a reapplication
of the loop detection checks and possible disabling of some transport
connections for new circuit establishment (not for existing circuits).

Possible Refinements (some necessary)
====================

1) Port-based disabling of the transport connection (TC)
   Consider the case where TC A-C is up first and A-D is disabled
   by rule (b).  Completely disabling A-D leaves no DLSw connectivity
   between LAN regions 1 and 5.  It would be a simple extension of
   the algorithm for D to note that TC A-D should be disabled only
   with respect to traffic to and from its port on LAN 4.

   Consider also that there may be source-routed LANs connected by
   a TC that forms a loop between TB LANs.  Again, it seems necessary
   to make the concept of disabling the TC specific to certain ports.

2) SSP exchange of "disable" message
   Consider the case where TC A-C is up, B-D is not, and A-D is
   coming up.  Node A applies rule (b) and can determine that
   A-D should be disabled, but node D has to move to rule (c)
   before it can see the same condition.  We could save node D
   the effort by having node A send a message containing the
   LAN region which forms a loop.

3) Protocol or SAP-based extensions to the scheme
   Because of SAP or protocol based bridge filters, the LAN topology
   may actually be different for SNA and NetBIOS.  The means for
   detecting loops and partially disabling transport connections
   may need to be extended so that different TC states can be kept
   for each protocol.

4) Transport connection failure
   If there were parallel transport connections (with one disabled)
   and the enabled one failed, the disabled TC should get enabled
   during its next periodic retry.  One could instead proactively
   execute the loop detection checks and seek to FIND and BRING UP
   a TC parallel to the one that failed.

5) Instability during region id changes
   We need to define how to avoid any temporary loops during the
   instability following LAN topology changes.

6) Handling parallel bridge paths
   We need to decide if we want to try to resolve the case where
   transport connection B-E is up then the customer adds a bridge
   between LAN regions 3 and 6.  B-E then becomes a transport
   connection within a single LAN region, disallowed by rule (a).
   This may be resolved successfully by triggering run-time capex
   from LAN region changes, and re-executing the loop-detection checks.

7) Format definitions
   Of course we need to define the format of region ids, the capex CVs
   and the frames on the LAN.  Included in the capex CV definition would
   be the old question of whether a run-time change would replace or
   simply add to/delete from the previously exchanged list.

8) Comparison with a full link state protocol
   Once one adds run-time capex and the like, this is getting more like
   a full LSP.  I believe it can be significantly simpler than one,
   but if we want to make sure we've thought of everything we should
   probably compare it to a standard routing protocol and make sure
   we can handle all the cases that can occur in our environment.

---

From: Choon Lee <[email-masked]>
Date: Mon, 23 May 1994 14:51:04 -0700

Peter,

Thank you for posting the "proposal" to the RIGlet. It looks very promising,
indeed. The "proactive" scheme has clear advantages (speedy circuit setup,
clearly defined paths), but also carries with it some baggages (periodic
loop detection frames, transitional loss of path at topology changes). 

My one comment on the proposal is that some of the items listed as "possible
refinement" need to be considered as essential for the scheme to work. In
particular, item 1, "port-based disabling of the transport connection" (I
think loss of connectivity between LANs would make the scheme much less
useful).

I agree that the intricate details would take some time to work out, and our
collective bandwidth is not sufficient to get it done before the June AIW.
I hope that once everyone who are interested in this subject matter has read
your proposal, we can gather several people to start work on refining your 
proposal.

Regards,
Choon Lee

>> From [email-masked] Tue May 17 15:52:56 1994
>> Date: Tue, 17 May 94 17:53:35 EDT
>> From: [email-masked]
>> To: [email-masked]
>> Subject:  Loop prevention ideas
>> Content-Length: 10644
>>